import functools
class Solution(object):
    def minInsertions(self, s):
        n = len(s)
        @functools.cache
        def dfs(i, j):
            if i >= j:
                return 0
            else:
                if s[i] == s[j]:
                    return dfs(i + 1, j - 1)
                else:
                    return 1 + min(dfs(i + 1, j), dfs(i , j - 1))

        return dfs(0, n - 1)
